|
In mathematics, in the area of discrete geometry, the no-three-in-line-problem, introduced by Henry Dudeney in 1917, asks for the maximum number of points that can be placed in the ''n'' × ''n'' grid so that no three points are collinear. This number is at most 2''n'', since if 2''n'' + 1 points are placed in the grid, then by the pigeonhole principle some row and some column will contain three points. ==Lower bounds== Paul Erdős (in ) observed that, when ''n'' is a prime number, the set of ''n'' grid points (''i'', ''i''2 mod ''n''), for 0 ≤ ''i'' < ''n'', contains no three collinear points. When ''n'' is not prime, one can perform this construction for a ''p'' × ''p'' grid contained in the ''n'' × ''n'' grid, where ''p'' is the largest prime that is at most ''n''. As a consequence, for any ε and any sufficiently large ''n'', one can place : points in the ''n'' × ''n'' grid with no three points collinear. Erdős' bound has been improved subsequently: show that, when ''n''/2 is prime, one can obtain a solution with 3(''n'' - 2)/2 points by placing points on the hyperbola ''xy'' ≡ ''k'' (mod ''n''/2) for a suitable ''k''. Again, for arbitrary ''n'' one can perform this construction for a prime near ''n''/2 to obtain a solution with : points. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「No-three-in-line problem」の詳細全文を読む スポンサード リンク
|